#include <iostream>
#include <algorithm>
#include <cstring>
#include <deque>
#include <set>


using namespace std;
using PII = pair<int, int>;

const int N = 11, M = N * N, E = 4010, P = (1 << 10);

int n, m, p, k;
int h[M], e[E], ne[E], w[E], idx;
int dist[M][P];
int st[M][P];
int g[N][N];
int key[M];
set<PII> edges;

void add(int a, int b, int c){
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx++;
}

void build(){
    int next[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    for (int i = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            for (int u = 0; u < 4; u ++){
                int nx = i + next[u][0], ny = j + next[u][1];

                if(!nx || nx > n || !ny || ny > m) continue;
                int a = g[i][j], b = g[nx][ny];
                if(!edges.count({a, b})){
                    add(a, b, 0);
                }
            }
        }
    }
}



int bfs(){
    memset(dist, 0x3f, sizeof dist);
    deque<PII> q;
    dist[1][0] = 0;
    q.push_back({1, 0});

    while(q.size()){
        PII temp = q.front();
        q.pop_front();

        int ver = temp.first, state = temp.second;
        if(st[ver][state]) continue;
        st[ver][state] = true;

        if(ver == g[n][m]){
            return dist[ver][state];
        }

        if(key[ver]){
            if(dist[ver][state | key[ver]] > dist[ver][state]){
                dist[ver][state | key[ver]] = dist[ver][state];
                int newstate = state | key[ver];
                q.push_front({ver, newstate});
            }
        }
        

        for (int u = h[ver]; u != -1; u = ne[u]){
            int j = e[u];

            if(w[u] && !((state >> (w[u] - 1)) & 1)) continue;

            if(dist[j][state] > dist[ver][state] + 1){
                dist[j][state] = dist[ver][state] + 1;
                q.push_back({j, state});
            }
            
        }
    }

    return -1;
}


int main()
{
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    cin >> n >> m >> p >> k;
    for (int i = 1, cnt = 1; i <= n; i ++){
        for (int j = 1; j <= m; j ++){
            g[i][j] = cnt ++;
        }
    }

    memset(h, -1, sizeof h);


    for (int i = 0; i < k; i ++){
        int a1, b1, a2, b2, g1;
        cin >> a1 >> b1 >> a2 >> b2 >> g1;
        int id1 = g[a1][b1], id2 = g[a2][b2];
        edges.insert({id1, id2});
        edges.insert({id2, id1});

        if(g1 != 0){
            add(id1, id2, g1);
            add(id2, id1, g1);
        }
    }

    build();

    int s;
    cin >> s;

    for (int i = 0; i < s; i ++){
        int a, b, c;
        cin >> a >> b >> c;
        key[g[a][b]] |= (1 << (c - 1));
    }

    int res = bfs();
    cout << res << endl;
    return 0;
}